package scala.examples.fs;

/*
 TODO: - type parameters
       - (partial) type application
       - pattern matching
       - lambda's
       - multi-methods
       - structural types
       - metaprogramming
*/
object Syntax {
  type Loc = int;  // TODO: parameterise Loc by the type of the value it references? (dependent types...) 
  var freshnessFactor = 0 // TODO: hack :-)

  trait ScopingConstruct[This] requires (This with ScopingConstruct[This]) {
    type this_ = (This with ScopingConstruct[This])
    def hasAsBoundName(n: String): Boolean 
    
    def mapOutsideScope(map: Map): This
    def newFromScopes(oldName: String, newName: String, termScopes: List[Term], typeScopes: List[Type], classSigScopes: List[ClassSig]): This 
    
    protected def termScopes: List[Term] = Nil
    protected def typeScopes: List[Type] = Nil
    protected def classSigScopes: List[ClassSig] = Nil
    
    // @result from is not a bound name, but to is
    def captures(from: String, to: Term): Boolean = !hasAsBoundName(from) && (to match {
      case Name(n2) => hasAsBoundName(n2)
      case _ => false
    })    
    
    // @result this term, with bound variable renamed so that captures(_,capturingTerm) == false
    // @pre captures(_, capturingTerm) --> we know capturingTerm is a Name 
    def avoidCapture(capturingTerm: Term): This = capturingTerm match { case Name(capturingName) =>
      assert(hasAsBoundName(capturingName))
      freshnessFactor = freshnessFactor+1
      val newN = capturingName+"$$"+freshnessFactor // TODO: might still clash
      
      newFromScopes(capturingName, newN, 
          for(val scope <- termScopes) yield subst(capturingName, Name(newN)) term scope, 
          for(val scope <- typeScopes) yield subst(capturingName, Name(newN)) typ scope,
          for(val scope <- classSigScopes) yield subst(capturingName, Name(newN)) classSig scope)
    }
   }
  
  trait AbstractArg
   case class Arg(name: String, typ: Type) extends AbstractArg
   case class TypeArg(name: String, kind: Kind) extends AbstractArg
   case class BoundedTypeArg(name: String, bound: Type) extends AbstractArg

  trait Term {
        // @result == true || @result == false
  	def isPath = false
  }
  
    trait BuiltinTerm extends Term // used as body of builtin members (during evaluation)
      case object BuiltinPrintln extends BuiltinTerm
      case object BuiltinPrint extends BuiltinTerm
      case object BuiltinError extends BuiltinTerm
    
    case class TypedTerm(term: Term, typ: Type) extends Term {
      override def isPath = term.isPath
    }
  
    trait Value extends Term;
      case object TBottom extends Value // TODO make parser recognize bot/unit --> fix in typer/eval
      case object TUnit extends Value
      case object Null extends Value
      case object True extends Value
      case object False extends Value
      case class StringLit(s :String) extends Value
      //case class IntLit(i :Int) extends Value;  

    // trait Path {}            
      case class Name(name: String) extends Term /*with Path*/ {
        override def isPath = true
      }
          
      case class Ref(x: Loc, name: String) extends Value /*with Path*/  {
        override def isPath = true
      }
  
      case class Select(e: Term, label: String) extends Term /*with Path if(e.isInstanceOf[Path])*/ {
        override def isPath = e.isPath 
      }

      

    case class Abstract(args :List[Arg], t: Type, body: Term) extends Value with ScopingConstruct[Abstract] {  // TODO: closure: escaping vars, ..
      def hasAsBoundName(n: String): Boolean = args.exists({case Arg(an, _) => an equals n case _ => false})
      
      def mapOutsideScope(map: Map): Abstract = Abstract(args, map.typ(t), body)       
      def newFromScopes(oldName: String, newName: String, termScopes: List[Term], typeScopes: List[Type], classSigScopes: List[ClassSig]): Abstract 
        = Abstract(subst(oldName, Name(newName)) args args, t, termScopes.head)
      
      override def termScopes = List(body)
    }
      
      
      
    case class Apply(fun: Term, actuals: List[Term]) extends Term;
    case class TypeAbstractTerm(args: List[BoundedTypeArg], t: Type, body: Term) extends Term with ScopingConstruct[TypeAbstractTerm] {
      def hasAsBoundName(n: String): Boolean = args.exists({case BoundedTypeArg(an, _) => an equals n case _ => false})
      
      def mapOutsideScope(map: Map): TypeAbstractTerm = TypeAbstractTerm(args, map.typ(t), body)       
      def newFromScopes(oldName: String, newName: String, termScopes: List[Term], typeScopes: List[Type], classSigScopes: List[ClassSig]): TypeAbstractTerm 
        = TypeAbstractTerm(subst(oldName, Name(newName)) args args, t, termScopes.head)
      
      override def termScopes = List(body)
    }
    
    case class TypeApplyTerm(fun: Term, actuals: List[Type]) extends Term
  
    case class New(p: Term) extends Term;
  
    case class LocalVal(name: String, tpe: Option[Type], value :Term, /*inscope(name)*/ scope: Term) extends Term with ScopingConstruct[LocalVal] {
      def hasAsBoundName(n: String): Boolean =  n equals name

      def mapOutsideScope(map: Map): LocalVal = LocalVal(name, map.option(map.typ,tpe), map.term(value), scope) 
      def newFromScopes(oldName: String, newName: String, termScopes: List[Term], typeScopes: List[Type], classSigScopes: List[ClassSig]): LocalVal 
         = LocalVal(newName, tpe, value, termScopes.head)
      
      override def termScopes = List(scope)       
    }
    
    case class ClassDef(name: String, /*inscope(name)*/ c: ClassSig, /*inscope(name)*/ e: Term) extends Term with ScopingConstruct[ClassDef] { // global variable
      def hasAsBoundName(n: String): Boolean =  n equals name
      
      def mapOutsideScope(map: Map): ClassDef = this
      def newFromScopes(oldName: String, newName: String, termScopes: List[Term], typeScopes: List[Type], classSigScopes: List[ClassSig]): ClassDef 
        = ClassDef(newName, classSigScopes.head, termScopes.head)
    
      override def termScopes = List(e)
      override def classSigScopes = List(c)
    }

    case class If(cond: Term, then: Term, els: Option[Term]) extends Term;

  trait Type;
          case class Inst(e: Term) extends Type
          case class Single(e: Term) extends Type
          case class Class(c: ClassSig) extends Type
          case class TypeSelect(t: Type, label: String) extends Type
          case class TypeAbstract(args: List[TypeArg], kind: Kind, /*inscope(args)*/ body: Type) extends Type with ScopingConstruct[TypeAbstract] {
            def hasAsBoundName(n: String): Boolean = args.exists({case TypeArg(an, _) => an equals n case _ => false})
            
            def mapOutsideScope(map: Map): TypeAbstract = TypeAbstract(args, map.kind(kind), body)       
            def newFromScopes(oldName: String, newName: String, termScopes: List[Term], typeScopes: List[Type], classSigScopes: List[ClassSig]): TypeAbstract 
              = TypeAbstract(subst(oldName, Name(newName)) args args, kind, typeScopes.head)
            
            override def typeScopes = List(body)
          }
          
          case class TypeApply(fun: Type, actuals: List[Type]) extends Type
          case class Any(kind: Kind) extends Type // maximal type for kind kind (Top(K))
          case class Bottom(kind: Kind) extends Type // minimal type for kind kind
          case class FunType(ts: List[Type]) extends Type
          case class All(name: String, bound: Type, /*inscope(name)*/ typ: Type) extends Type with ScopingConstruct[All] {
            def hasAsBoundName(n: String): Boolean = name equals n 
            
            def mapOutsideScope(map: Map): All = All(name, map.typ(bound), typ)       
            def newFromScopes(oldName: String, newName: String, termScopes: List[Term], typeScopes: List[Type], classSigScopes: List[ClassSig]): All 
              = All(newName, bound, typeScopes.head)
            
            override def typeScopes = List(typ)
          }
          case class BuiltinTypeFs extends Type // the type of the builtin variable $fs$
          
  trait Kind
          case object StarKind extends Kind
          case class FunKind(ks: List[Kind]) extends Kind // classifies TypeAbstract's
          // TODO decide whether we want to curry everything (FunKind takes only two kinds) or just use list
          

  trait StoreItem;
          case class ClassSig(ps: List[Term], self: String, selfT: Type, ms: List[Member]) 
               extends StoreItem {
            // should  store an explicit nominal self type, but in case of a stand-alone class signature, 
            // parser passes null for selfT as it can't provide a nominal type
            // not too happy about this, but necessary, as giving 'this' a structural type doesn't work (no longer related to the corresponding nominal type)
            // (but that's the only option if you don't include an explicit type)
            val selfType = if(selfT==null) Class(this) else selfT
          }
          case class Obj(c: Term, ms: List[Member]) extends StoreItem;

          
  // TODO: make hierarchy more elegant, but need some way to easily match on Val[def/dcl] --> need common superclass 
  // good case for views for pattern matching
  trait Member {
    def label: String
    def signature: Member
    def corresponds(other: Member): Boolean = this.label equals other.label // TODO: make more precise (i.e., simple cases, in case of overloading, ...)
  }
  
  trait Declaration extends Member {
    def signature = this
  }
  
  trait Definition extends Member;

  case class ValSig(l: String, t: Type, value: Option[Term]) extends Member { 
    def label = l
    def signature: Member = new ValSig(l,t,None)
  }
  
  class ValDcl(l: String, t: Type) extends ValSig(l, t, None) with Declaration {
    override def signature = this
  }
  class ValDef(l: String, t: Type, e: Term) extends ValSig(l, t, Some(e)) with Definition {
    override def signature: Member = new ValDcl(l,t)
  }

  case class DefSig(l: String, args :List[Arg], t: Type, body: Option[Term]) extends Member { 
    def label = l
    def signature: Member = new DefSig(l, args, t, None)
  }
  
  class DefDcl(l: String, args :List[Arg], t: Type)  extends DefSig(l, args, t, None) with Declaration {
    override def signature = this
  }
  
  class DefDef(l: String, args :List[Arg], t: Type, body: Term) extends DefSig(l, args, t, Some(body)) with  Definition {
    override def signature: Member = new DefDcl(l, args, t)
  }

  
  case class TypeDcl(l: String, upperbound: Option[Type]) extends Member with Declaration {
    upperbound match { case Some(_) => error("Type declarations with upper-bound not handled yet") case _ =>} // TODO
    def label = l
    override def signature = this
  }
  
  case class TypeDef(l: String, t: Type) extends Member with Definition {
    def label = l
    override def signature = this
  }

  def ValSigCtor(m: ValSig) = (m match { case ValSig(l,t,o) => &ValSig_ case o: ValDcl => &ValDcl_ case o: ValDef => &ValDef_})
  def ValDcl_(l: String,  t: Type, o: Option[Term]) = o match { case None => new ValDcl(l, t)}
  def ValDef_(l: String,  t: Type, o: Option[Term]) = o match { case Some(e) => new ValDef(l, t, e)}
  def ValSig_(l: String,  t: Type, o: Option[Term]) = ValSig(l, t, o)
  def ValDcl(l: String,  t: Type) = new ValDcl(l, t)
  def ValDef(l: String,  t: Type, e: Term) = new ValDef(l, t, e)

  def DefSigCtor(m: DefSig) = (m match { case DefSig(l,a,t,o) => &DefSig_ case o: DefDcl => &DefDcl_ case o: DefDef => &DefDef_})
  def DefDcl_(l: String,  args :List[Arg], t: Type, o: Option[Term]) = o match { case None => new DefDcl(l, args, t)}
  def DefDef_(l: String,  args :List[Arg], t: Type, o: Option[Term]) = o match { case Some(e) => new DefDef(l, args, t, e)}
  def DefSig_(l: String,  args :List[Arg], t: Type, o: Option[Term]) = DefSig(l, args, t, o)
  def DefDcl(l: String, args :List[Arg], t: Type)  = new  DefDcl(l, args, t)
  def DefDef(l: String, args :List[Arg], t: Type, body: Term) = new DefDef(l, args, t, body)


  
  // maps from locations --------------------------------------------------

    class LocMap[T <: AnyRef] {
      val nextLoc: Loc = 0;
      def apply(n: Loc): T = null;
      def update(n: Loc, newitem: T): LocMap[T] = null;

      // result(old.nextLoc) == item
      def extend(item: T): LocMap[T] = new LocMap[T] {
        override val nextLoc: Loc = 
          LocMap.this.nextLoc + 1;
        override def apply(n: Loc): T = 
          if (n == nextLoc-1) item else LocMap.this.apply(n);
        override def update(n: Loc, newitem: T): LocMap[T] = 
          if (n == nextLoc-1) LocMap.this.extend(newitem)
          else LocMap.this.update(n, newitem).extend(item)
      }
    }
  // maps & substitution ----------------------------------------------

    	// perfect candidate for DGP! -- this class would be unnecessary
  class Map {
    def term(e: Term): Term = e match {
      case Select(e1, l) => Select(term(e1), l)
      case New(p) => New(term(p))
      case LocalVal(name, optType, value, scope) => LocalVal(name, option(typ,optType), term(value), term(scope))
      case ClassDef(n, c, e) =>	ClassDef(n, classSig(c), term(e))
      case If(cond, then, optElse) => If(term(cond), term(then), option(term,optElse))
      case Abstract(args :List[Arg], t: Type, body: Term) => Abstract(this.args(args), typ(t), term(body))
      case Apply(fun, actuals)  =>  Apply(term(fun), actuals map term)    
      case TypeAbstractTerm(args: List[BoundedTypeArg], t: Type, body: Term) => TypeAbstractTerm(this.args(args), typ(t), term(body))
      case TypeApplyTerm(fun: Term, actuals: List[Type]) => TypeApplyTerm(term(fun), actuals map typ)    

      case TypedTerm(e, t)  =>  TypedTerm(term(e), typ(t))    
      case _ => e
    }
    
    def classSig(c: ClassSig): ClassSig = c match {
      case c @ ClassSig(ps, self, st, ms) =>
	ClassSig(ps map term, self, (if(st!=null)  typ(st) else null), ms map member)
    }
    
    def typ(t: Type): Type = t match {
      case Inst(e)          => Inst(term(e))
      case Single(e)        => Single(term(e))
      case Class(c)         => Class(classSig(c))
      case TypeSelect(t, l) => TypeSelect(typ(t), l)
      case FunType(ts) => FunType(ts map typ)
      case TypeAbstract(args: List[TypeArg], kind: Kind, body: Type)   => TypeAbstract(this.args(args), this.kind(kind), typ(body))
      case TypeApply(fun: Type, actuals: List[Type])                   => TypeApply(typ(fun), actuals map typ)    
      case Any(kind: Kind)                                             => Any(this.kind(kind)) 
      case Bottom(kind: Kind)                                          => Bottom(this.kind(kind))
      case All(name: String, bound: Type, /*inscope(name)*/ typ: Type) => All(name, this.typ(bound), this.typ(typ))     
      case _ => t
    }
    
    def kind(k: Kind): Kind = k match {
      case StarKind => StarKind
      case FunKind(ks: List[Kind]) => FunKind(kinds(ks))
    }

    def kinds(ks: List[Kind]): List[Kind] = for(val k <- ks) yield kind(k)    
    
    def option[t,s](fun: t=>s, o: Option[t]) :Option[s] = o match {
      case Some(obj) => Some(fun(obj))
      case None => None
    }
    
    def member(m: Member): Member= m match { // TODO: why doesn't GADT mechanism work?
      case ValSig(l, t, o)    => ValSigCtor(m.asInstanceOf[ValSig])(l, typ(t), option(term, o))
      case DefSig(l, args, t, o) => DefSigCtor(m.asInstanceOf[DefSig])(l, args map {case Arg(n,at) => Arg(n,typ(at))}, typ(t),option(term, o))
      case TypeDcl(l, t)   => TypeDcl(l, option(typ,t))
      case TypeDef(l, t)   => TypeDef(l, typ(t))
    }
    def members(ms: List[Member]): List[Member] = for(val m <-ms) yield member(m)
    
    def arg[t <: AbstractArg](a: t): t = a match {
      case Arg(name, typ) => Arg(name, this.typ(typ))
      case TypeArg(name, kind) => TypeArg(name, this.kind(kind))
      case BoundedTypeArg(name, bound) => BoundedTypeArg(name, typ(bound))
    }
  
    def args[t <: AbstractArg](as: List[t]): List[t] = for(val a <- as) yield(arg(a))
  }

  	/* e.map( Name(name) => to |||  
                  New(name, p, e) => e  |||
                  ClassDef(name, c, e) => e |||
                  ClassSig(ps, name, ms) => ClassSig(ps map term, name, ms))
            // order of traversal is important!
	            // once a ClassSig has been visited, don't traverse its members
	            // 
  	*/	

  class Once[a] {
     var done = false
     var res: a = _
     def once(fun: =>a): a = {if(!done){res=fun; done=true}; res}
  }
          
  def subst(name: String, to: Term) :Map = new Map {
    val shownScope = new Once[unit]
    debug("<subst name=\""+name+"\" to=\""+to+"\">")
    

    
    override def member(m: Member): Member = {
      var showNew=false
      shownScope.once{debug("<orig>"+(show member m)+"\n</orig>"); showNew=true}
      
      val r = super.member(m)

      if(showNew)
        debug("<new>"+(show member r)+"\n</new>\n</subst>\n")
      r
    }
    
    /*
      {     
      var showNew=false
      shownScope.once{debug("<orig>"+(show term e)+"\n</orig>"); showNew=true}

      val r = term2(e)
          
      if(showNew)
        debug("<new>"+(show term r)+"\n</new>\n</subst>\n")
        
      r
      }
      */
    override def term(e: Term): Term = e match {
       // note that Select is properly handled by recursion: only the target of the select may contain a name  that may get subst'ed, the label is an inert string
       case Name(n) if (name == n) => to
       
       case _ => if(e.isInstanceOf[ScopingConstruct[Term]]) {
          val scopingConstruct: ScopingConstruct[Term] = e.asInstanceOf[ScopingConstruct[Term]]
          
          // avoid capture: if we're renaming some free variable in our scope *to* our bound variable, first change our bound name 
          if(scopingConstruct.captures(name, to))
            term(scopingConstruct.avoidCapture(to))

          // subst'ing bound name: subst outside scope  
          else if(scopingConstruct.hasAsBoundName(name))
            scopingConstruct.mapOutsideScope(this)
          
          else super.term(e)
        }
        else super.term(e)
    }
  
    
    override def typ(t: Type): Type = if(t.isInstanceOf[ScopingConstruct[Type]]) {
      val scopingConstruct: ScopingConstruct[Type] = t.asInstanceOf[ScopingConstruct[Type]]
       if(scopingConstruct.captures(name, to))
         typ(scopingConstruct.avoidCapture(to))
       else if(scopingConstruct.hasAsBoundName(name))
         scopingConstruct.mapOutsideScope(this)
       else super.typ(t)       
    }
    else super.typ(t)
    
    override def classSig(c: ClassSig): ClassSig = {
      var showNew=false
      shownScope.once{debug("<orig>"+(show classSig c)+"\n</orig>"); showNew=true}
      
      val r = c match {
        // avoid capture
        case ClassSig(ps, n, st, scope) if (name != n && (to match { case Name(n2) => n == n2 case _ => false})) => 
          val newN = n+"_"
          val newScope = subst(n, Name(newN)) members scope
          classSig(ClassSig(ps, newN, st, newScope))
        
        case ClassSig(ps, n, st, scope) if name == n =>  // self name is bound in members
           ClassSig(ps map term, n, st, scope)
           
        case _ => super.classSig(c)
      }

      if(showNew)
        debug("<new>"+(show classSig r)+"\n</new>\n</subst>\n")
        
      r
    }
    
    override def arg[t <: AbstractArg](a: t): t = to match { case Name(n2)  => a match {
      case Arg(name, typ) if name equals n2 => Arg(n2, typ)
      case TypeArg(name, kind) if name equals n2 => TypeArg(n2, kind)
      case BoundedTypeArg(name, bound) if name equals n2 => BoundedTypeArg(n2, bound)
      case _ => a
    }}
  }
	       


  // pretty printing -------------------------------------------------------
	 // generic fold with + as combinator 
	 // (could you also interpret this in the string concatenation idiom ??)
  class Show(indent: String) {
    private val delta = "  ";

    def newLine: String = "\n" + indent;

    def term(e: Term): String = e match {
      case Null => "null"
      case Name(x) => x
      case True => "true"
      case False => "false"
      case StringLit(s) => "\"" + s + "\""
      case If(cond, then, Some(els)) => "if(" + term(cond) + ") " + atomicTerm(then) + " else " + atomicTerm(els)
      case If(cond, then, None) =>  "if(" + term(cond) + ") " + term(then)
      case Apply(fun, actuals) => term(fun) + actuals.map(term).mkString("(", ", ", ")")
      case Select(e1, l) => atomicTerm(e1) + "." + l;
      case Ref(x, n) => "*("+n+")"
      case LocalVal(name, Some(tpe), value, scope) => "(val " + name + ": " + typ(tpe) + " = " + term(value) + "); "+term(scope) 
      case LocalVal(name, None, value, scope) => "(val " + name + " = " + term(value) + "); "+term(scope)
      case New(p) => 
	"new " + term(p) 
      case ClassDef(x, c, e) => 
	"class " + x + " extends " + classSig(c) + ";" + newLine + term(e)
      case TypedTerm(e, t)  => atomicTerm(e) + ": "+ typ(t)   
      case Abstract(args :List[Arg], t: Type, body: Term) => "(("+this.args(args)+") => "+term(body)+": "+ typ(t) +")"
      case TypeAbstractTerm(args: List[BoundedTypeArg], t: Type, body: Term) => "(["+this.args(args)+"] => "+term(body)+": "+ typ(t) +")"
      case TypeApplyTerm(fun: Term, actuals: List[Type]) => term(fun)+actuals.map(typ).mkString("[", ", ", "]")
      
      case x => if(x==null) "null" else x.toString
    }
        
    def atomicTerm(e: Term): String = e match {
      case LocalVal(_, _, _, _) | ClassDef(_, _, _) => "(" + term(e) + ")"
      case _ => term(e)
    }
    def classSig(c: ClassSig): String = c match {
      case ClassSig(ps, self, st, ms) =>
	val show1 = new Show(indent + delta);
	ps.map(term).mkString("", ", ", "{ ") + self + (if(st!=null) ": " + typ(st) else "") +
	ms.map(show1.member).mkString(" | ", "", newLine) + "}"
    }
    
    def typ(t: Type): String = t match {
      case Inst(e)          => term(e) + ".inst"
      case Single(e)        => term(e) + ".type"
      case Class(c)         => "class " + classSig(c)
      case TypeSelect(t, l) => typ(t) + "#" + l;
      case FunType(ts) => (ts map typ).mkString("","=>","")

      case TypeAbstract(args: List[TypeArg], kind: Kind, body: Type)   => "(["+this.args(args)+"] => "+typ(body)+": "+ this.kind(kind) +")"
      case TypeApply(fun: Type, actuals: List[Type])                   => typ(fun)+actuals.map(typ).mkString("[", ", ", "]")
      case All(name: String, bound: Type, /*inscope(name)*/ typ: Type) => "All("+name+" <: "+this.typ(bound)+")" + this.typ(typ)
      
      case Any(kind: Kind)                                             => "Any("+this.kind(kind)+")" 
      case Bottom(kind: Kind)                                          => "Bottom("+this.kind(kind)+")" 
      
      case BuiltinTypeFs() => "$FS$"
    }
    
    def args(as: List[AbstractArg]) :String = (for(val a <- as) yield arg(a)).mkString("", ", ", "")
    
    def arg(a: AbstractArg): String =  a match {
      case Arg(name, typ) =>  name+": "+this.typ(typ)
      case TypeArg(name, kind) => name+": "+this.kind(kind)
      case BoundedTypeArg(name, bound) =>  name+"<: "+this.typ(bound)
    }

    def kind(k: Kind): String = k match {
      case StarKind => "*"
      case FunKind(ks: List[Kind]) => kinds(ks).mkString("", "=>", "")
    }

    def kinds(ks: List[Kind]): List[String] = for(val k <- ks) yield kind(k)    

    def option[t](fun: t=>String, o: Option[t]) :String = o match {
      case Some(obj) => fun(obj)
      case None => ""
    }
  
    def members(ms: List[Member]): String = {
      (for(val m <-ms) yield member(m)).mkString("","\n","")
    }
    
    def member(m: Member): String = newLine + (m match {
      case ValSig(l, t, b) => 
	"val " + l + ": " + typ(t) + option(((x :Term) => " = "), b) + option(atomicTerm, b)
      case DefSig(l, a, t, b) => 
        "def " + l + args(a) + ": " + typ(t) + option(((x :Term) => " = "), b) + option(atomicTerm, b)
      case TypeDcl(l, t) => 
	"type " + l + option(((x :Type) => " <: "),t) + option(typ,t)
      case TypeDef(l, t) => 
	"type " + l + " = " + typ(t)
    });
  }
  val show = new Show("");
  
  
  def debug[t,a](s :t):a =  null //Debug.syntax.log(s)
  
  def showTree[T](e :T) :String = {
    var i = 0
    def twoParens(c :Char) :Boolean = {if(c equals '(') i=i+1; if(i>1) false else true}
    e.toString.toList.takeWhile(twoParens).mkString("","","")
  }
}
